package com.study;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-10-28 09:27
 * @version: 1.0
 * @description: 反转链表
 * 刚开始链最后一个元素的 next 为空，反转之后让链表的头指针的 next 为空
 * 需要一个中间变量存储交换中的元素
 **/
public class ReverseLink {

	static class Node{
		int value;
		Node next;

		public Node(int value, Node next) {
			this.value = value;
			this.next = next;
		}

		@Override
		public String toString() {
			return "Node{" +
					"value=" + value +
					", next=" + next +
					'}';
		}
	}


	public static void main(String[] args) {
		Node node1 = new Node(1, null);
		Node node2 = new Node(2, node1);
		Node node3 = new Node(3, node2);
		Node node4 = new Node(4, node3);
		Node node5 = new Node(5, node4);

		System.out.println(linkedFindLast(node1));

		System.out.println(node5);
//		Node n = recursion(node5);
		Node n = reverse(node5);
		System.out.println(n);
		System.out.println(linkedFindLast(node1));

	}

	/**
	 * 查询链表末端
	 * @param node
	 * @return
	 */
	static Node linkedFindLast(Node node){
		for (Node r = node,p;;){
			if ((p = r.next) == null){
				return r;
			}
			r = p ;
		}
	}

	private static Node reverse(Node head) {
		Node prev = null,next,curr = head;

		while (curr != null){
			next = curr.next;
			curr.next = prev;
			prev = curr;
			curr = next;
		}
		return prev;
	}

	//递归
	public static Node recursion(Node head){
        if(head == null || head.next == null){
			return head;
        }else {
	        Node newHead = recursion(head.next);
			head.next.next = head;
	        head.next = null;
			return newHead;
        }
	}

	public static Node recursion1(Node head){
		if (head == null || head.next == null){
			return head;
		}
		Node node = recursion1(head.next);
		head.next.next = head;
		head.next = null;
		return node;
	}

}
